package com.ww.springboot.boot.algorithm.dp;

import java.util.HashMap;
import java.util.Map;

/**
 * 描述：斐波那契
 * <p>
 * 除了第一 第二个数是1 1 其余的数都是前两个数之和
 * 1 1 2 3 5 8 13
 *
 * 例:两只兔子 生一对兔子 生长期 2个月
 *
 * @author wanwei
 * @since 2021-07-19 19:13
 */
public class FbnqDemo {

    public static void main(String[] args) {
        //method1();

        method2();
    }

    /**
     * 递归代码简单 但是遍历层次太深 重复计算太多
     * 10
     * 9*1          8*1
     * 8*1       7*1   7*1    6*1  2^n次
     * <p>
     * 1:优化1 加一个map存储数据 避免重复计算
     */
    private static void method2() {
        Map<Integer, Long> map = new HashMap<>();
        for (int i = 1; i <= 92; i++) {
            Long total = num(i, map);
            map.put(i, total);
            System.out.println(i + ":" + total);
        }
    }

    private static Long num(int i, Map<Integer, Long> map) {
        if (i == 1L || i == 2L) {
            return 1L;
        }
        Long total = 0L;
        Long total_2 = map.get(i - 2);
        if (total_2 != null) {
            total += total_2;
        } else {
            total += num(i - 2, map);
        }
        Long total_1 = map.get(i - 1);
        if (total_1 != null) {
            total += total_1;
        } else {
            total += num(i - 1, map);
        }
        return total;
    }

    /**
     * 平推
     */
    private static void method1() {
        Long n = 1L, m = 1L;
        for (int i = 3; i <= 92; i++) {
            if (i == 1 || i == 2) {
                System.out.println(i + ":" + 1);
            }
            Long newN = n + m;
            m = n;
            n = newN;
            System.out.println(i + ":" + n);
        }
    }


}
